/*
 * @lc app=leetcode.cn id=654 lang=swift
 *
 * [654] 最大二叉树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    func constructMaximumBinaryTree(_ nums: [Int]) -> TreeNode? {
        if nums.count == 0 { return nil}

        func constructMaximumBinaryTree(_ nums: [Int], _ lo: Int, _ hi: Int) -> TreeNode? {
            if lo > hi { return nil }

            var index = -1, max = Int.min
            // 找到最大值
            for i in lo...hi {
                if nums[i] > max {
                    index = i
                    max = nums[i]
                }
            }

            let root = TreeNode(max)
            root.left = constructMaximumBinaryTree(nums, lo, index-1)
            root.right = constructMaximumBinaryTree(nums, index+1, hi)

            return root
        }

        return constructMaximumBinaryTree(nums, 0, nums.count-1)
    }
}
// @lc code=end

